Deadlock is a pernicious condition in which multiple processes are prohibited from making progress, because each is waiting for one or more resources that are being used by some other process. However, deadlock is difficult to detect because it may occur only under specific conditions involving, for example, the interleaving or timing of the executing threads.
In a simple example of deadlock, an operating system contains two files, file1 and file2. Two concurrently running processes, thread1 and thread2, both require file1 and file2 to complete successfully. If thread1 opens file1, and thread2 opens file2, deadlock may result when thread1 attempts to open file2 before closing file1, and thread2 attempts to open file1 before closing file2. Thus, the two processes could wait forever.
Several authors have provided characterizations of deadlock through the application of fundamental assumptions regarding concurrently running threads that require various resources, see, for example, W. W. Collier, “System Deadlocks,” Tech. Rep. TR-00.1756, IBM Systems Development Division, New York, 1968; J. W. Havender, “Avoiding Deadlock in Multitasking Systems,” IBM Syst. J. 7, 2 (1968), pp. 74-84; J. E. Murphy, “Resource Allocation with Interlock Detection in a Multi-Task System,” In Proc. FJCC, AFIPS (1968), vol. 33; and A. Shoshani et al., “Prevention, Detection, and Recovery from System Deadlocks,” In Proceedings of the Fourth Annual Princeton Conference on Information Sciences and Systems (March 1970).
Three such fundamental assumptions that may be made about concurrently running threads include:
1) Mutual exclusion—threads claim exclusive control of the resources they require;
2) Wait for—threads hold resources already allocated to them, and must await additional required resources; and
3) No preemption—resources cannot be forcibly removed from the threads holding them until the resources are used to completion.
In the context of the Java™ language (Sun Microsystems, Inc.), the three fundamental assumptions described above are satisfied and the resources of interest are locks.
When these fundamental assumptions hold, deadlock may be characterized by a resource graph, see, for example W. W. Collier; J. W. Havender; J. E. Murphy; and A. Shoshani et al. A graph is defined as a pair (N, E), where N is a set of nodes and E is a set of edges. If there are n distinct resources, the graph has n nodes, with each node representing a single resource. Each edge is of the form (v, w), where vεN and wεN. Edge (v,w) extends from node v to node w if there exists a thread with an execution path that acquires resource v and subsequently requests resource w. A path in a graph is a set {(vi,vi+1)|i=1, . . . n} of edges, where n≧1. A cycle is a path in which v1, . . . , vn are all distinct, and vn+1=v1.
Assuming that a thread does not request a resource it has already acquired, if deadlock occurs, then the resource graph contains at least one cycle. In the context of programming languages, such as Java™, the use of the graph may be termed a lock cycle strategy, because of the search for cycles of lock acquisitions and requests.
Therefore it would be desirable to automatically determine whether deadlock will occur through source and object code of a multithreading program without having to execute the code of the multithreading program.